1. Field of the Invention
The present invention relates to the design of computer networks. More specifically, the present invention relates to a method and an apparatus that prevents loops from occurring when spanning tree configuration messages are lost while executing a spanning tree protocol across bridges in a network.
2. Related Art
Computer networks are frequently coupled together through transparent bridges. The most basic form of transparent bridge is one that attaches to two or more local area networks (LANs) (each attachment to a bridge is referred to as a “port”). Such a bridge listens promiscuously to every packet transmitted and stores each received packet until it can be transmitted on the LANs other than the one on which it was received.
The transparent bridge was developed to allow stations that were designed to operate on only a single LAN to work in a multi-LAN environment. The stations expect to transmit a packet, exactly as they would in a single-LAN environment, and have the packet delivered. The bridge must therefore transmit the packet exactly as received. If the bridge modified the packet in any way—for example, by overwriting the source address portion of the header with its own address—then protocols on stations might not work properly.
Note that bridges can potentially cause a packet to loop, which can cause the packet to replicate exponentially. This replication can increase congestion on the network to the point where the network stops functioning.
This looping problem is commonly dealt with by using a spanning tree protocol defined in Institute of Electrical and Electronics Engineers (IEEE) standard 802.1D. This spanning tree protocol operates by having bridges dynamically discover a subset of the network topology that is loop-free (a tree) and yet has enough connectivity so that, where physically possible, there is a path between every pair of LANs (the tree is spanning).
The basic idea behind the spanning tree protocol is that bridges periodically transmit special configuration messages to each other that allow them to calculate a spanning tree. Referring to FIG. 2, these configuration messages contain enough information to allow bridges to do the following. (1) Elect a single bridge among all bridges on all LANs, to be the root bridge (step 202). (2) Calculate the distance of shortest path from themselves to the root bridge (step 204). (3) Elect a designated bridge on each LAN from the bridges residing on that LAN (step 206), wherein the elected bridge is the one closest to the root bridge and will forward packets to the root bridge. (4) Choose a port for each bridge that gives the best path to the root bridge (step 208). (5) Select ports on each bridge to be included in the spanning tree (step 210). (6) Place selected ports into a forwarding state in which messages are forwarded to and from the port (step 212). (7) Place other ports into a backup state, in which messages are not forwarded to or from the port (step 214).
This protocol can be summarized in the following poem entitled “Algorhyme” by Radia Perlman, the inventor of the present invention.                I think that I shall never see        A graph more lovely than a tree.        A tree whose crucial property        Is loop free connectivity.        A tree that must be sure to span        So packets can reach every LAN.        First, the root must be selected.        By ID, it is elected.        Least-cost paths from root are traced.        In the tree, these paths are placed.        A mesh is made by folks like me,        Then bridges find a spanning tree.        
It is important to engineer a bridge with sufficient CPU power so that if the network becomes congested, the spanning tree protocol will operate properly. Otherwise, the network becoming temporarily congested might cause configuration messages to become lost, which can cause the spanning tree protocol to incorrectly turn extra bridge ports on. This can cause loops, which can dramatically increase the amount of congestion to such a point that the spanning tree protocol never recovers.
Unfortunately, the IEEE 802.1D standard does not specify a performance requirement, and as a result, some of the bridge hardware that is presently deployed is not capable of processing spanning tree configuration messages during worst-case traffic. Consequently, messages can be lost and loops can be created.
Hence, what is needed is a method and an apparatus that prevents loops from occurring when spanning tree configuration messages are lost.